Bá Vương biệt cơ đã được lên kế hoạch thực hiện từ năm 1988. Ý tưởng thực hiện bộ phim xuất phát từ chính Trương Quốc Vinh. Anh đọc được tiểu thuyết cùng tên của Lý Bích Hoa, và nhờ người quản lý liên lạc với Từ Phong - nhà sản xuất bộ phim - đề nghị hợp tác thực hiện một bộ phim dựa theo tiểu thuyết này. Từ Phong liên lạc với Trần Khải Ca và mời ông làm đạo diễn cho bộ phim. Ban đầu, người dự định được chọn vào vai Đoàn Tiểu Lâu là Thành Long, nhưng công ty quản lý e ngại vai diễn có tính chất đồng tính sẽ làm ảnh hưởng đến hình ảnh của anh nên đã từ chối. Lý Bích Hoa tuyên bố rằng nếu không phải là Trương Quốc Vinh vào vai Trình Điệp Y thì bà sẽ không để tiểu thuyết của mình được dựng thành phim. Riêng Trương Quốc Vinh thì cho rằng, mình không đủ đẹp để diễn một Trình Điệp Y được miêu tả trong tiểu thuyết (nhân vật Trình Điệp Y được Viên đại nhân ngợi ca trong tiểu thuyết với những câu: "Một nụ cười đem đến cả mùa xuân. Một giọt lệ làm đen tối đất trời... Chỉ có nàng, chỉ có nàng mới có được vẻ đẹp nhường ấy...").

Đến năm 1991, ứng cử viên hàng đầu cho vai Trình Điệp Y là nam diễn viên Tôn Long. Tuy nhiên, do một số vấn đề, cuối cùng vai diễn này không được giao cho anh. Về sau, Từ Phong cho biết bà cảm thấy vẻ đẹp cứng cỏi của Tôn Long không phù hợp với nhân vật Trình Điệp Y [4]. Trần Khải Ca sau đó đã đề cử nam diễn viên Lôi Hán, nhưng anh lại không qua được vòng phỏng vấn (mặc dù sau này vẫn tham gia bộ phim với vai người học trò của Trình Điệp Y). Cho đến một ngày, một người bạn ở Hồng Kông gởi đến cho Trần Khải Ca tờ tạp chí City Magazine (số kỷ niệm 15 năm phát hành - 1991). Trên trang bìa là hình ảnh Trương Quốc Vinh trong trang phục vai Đán của vở Kinh kịch Kỳ tương hội (奇雙會), với một dòng chú thích: "Khải Ca, liệu anh có bị mê hoặc?". Chính bức ảnh này đã khiến Trần Khải Ca quyết định giao vai Trình Điệp Y cho Trương Quốc Vinh. Trương Quốc Vinh đã đến Bắc Kinh sáu tháng để học Kinh kịch và tham gia bộ phim, đây cũng là lần đầu tiên một diễn viên Hồng Kông được mời vào một phim của Trung Quốc đại lục.